package com.cb2.algorithm.leetcode;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/is-array-a-preorder-of-some-binary-tree'>数组是否表示某二叉树的前序遍历(Is Array a Preorder of Some Binary Tree)</a>
 * <p>给定一个以 0 为起始索引的整数 二维数组 nodes ，你的任务是确定给定的数组是否表示某个 二叉 树的 前序 遍历。</p>
 * <p>对于每个索引 i ，nodes[i] = [id, parentId] ，其中 id 是索引 i 处节点的 id，parentId 是其在树中的父节点 id（如果该节点没有父节点，则 parentId = -1 ）。</p>
 * <p>如果给定的数组表示某个树的前序遍历，则返回 true ，否则返回 false 。</p>
 * <p>注意：树的 前序 遍历是一种递归的遍历方式，它首先访问当前节点，然后对左子节点进行前序遍历，最后对右子节点进行前序遍历。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *
 *      输入：nodes = [[0,-1],[1,0],[2,0],[3,2],[4,2]]
 *      输出：true
 *      解释：给定的 nodes 数组可以构成下面图片中的树。
 *                          0
 *                        /   \
 *                       1     2
 *                           /   \
 *                          3     4
 *      我们可以验证这是树的前序遍历，首先访问节点 0，然后对左子节点进行前序遍历，即 [1] ，然后对右子节点进行前序遍历，即 [2,3,4] 。
 *
 *  示例 2：
 *      输入：nodes = [[0,-1],[1,0],[2,0],[3,1],[4,1]]
 *      输出：false
 *      解释：给定的 nodes 数组可以构成下面图片中的树。
 *                          0
 *                        /   \
 *                       1     2
 *                     /   \
 *                   3      4
 *      对于前序遍历，首先访问节点 0，然后对左子节点进行前序遍历，即 [1,3,4]，但是我们可以看到在给定的顺序中，2 位于 1 和 3 之间，因此它不是树的前序遍历。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nodes.length <= 10^5</li>
 *     <li>nodes[i].length == 2</li>
 *     <li>0 <= nodes[i][0] <= 10^5</li>
 *     <li>-1 <= nodes[i][1] <= 10^5</li>
 *     <li>生成的输入保证 nodes 可以组成二叉树。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/16 13:30
 */
public class LC2764IsArrayAPreorderOfSomeBinaryTree_M {
    static class Solution {
        private final Map<Integer, List<Integer>> graph = new HashMap<>();
        private List<List<Integer>> preorderNodes;
        private int currIdx;

        /**
         * 此方法检查给定的节点列表是否代表二叉树的有效前序遍历。
         */
        public boolean isPreorder(List<List<Integer>> nodes) {
            this.preorderNodes = nodes;
            // 构建一个表示树的图；键是父节点，值是子节点。
            for (List<Integer> node : nodes) {
                graph.computeIfAbsent(node.get(1), k -> new ArrayList<>()).add(node.get(0));
            }
            // 从根节点（假设位于列表的第一个位置）开始执行深度优先搜索，并验证前序遍历是否与输入列表匹配。
            boolean isValidPreorder = dfs(preorderNodes.get(0).get(0)) && currIdx == nodes.size();
            // 重置索引以供将来调用
            currIdx = 0;
            return isValidPreorder;
        }

        private boolean dfs(int nodeVal) {
            if (nodeVal != preorderNodes.get(currIdx).get(0)) {
                return false;
            }
            currIdx++;
            // 检查当前节点是否与索引 currentIndex 处的 preorderNodes 中的当前节点匹配。
            for (int child : graph.getOrDefault(nodeVal, new ArrayList<>())) {
                if (!dfs(child)) {
                    return false;
                }
            }
            // 递归访问所有子节点。
            return true;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isPreorder(Arrays.asList(
                Arrays.asList(0, -1),
                Arrays.asList(1, 0),
                Arrays.asList(2, 0),
                Arrays.asList(3, 2),
                Arrays.asList(4, 2)
        )));

        System.out.println(solution.isPreorder(Arrays.asList(
                Arrays.asList(0, -1),
                Arrays.asList(1, 0),
                Arrays.asList(2, 0),
                Arrays.asList(3, 1),
                Arrays.asList(4, 1)
        )));
    }
}
